package com.yvon.service.demo.algorithm.offer;


import com.yvon.service.demo.algorithm.offer.ext.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 */
public class P07 {
    public static void main(String[] args) {
        Solution solution = new P07().new Solution();
        int[] preorder = new int[] {3,9,20,15,7};
        int[] inorder = new int[] {9,3,15,20,7};
        TreeNode node = solution.buildTree(preorder, inorder);
        TreeNode.prePrint(node);

    }

    /**
     * 前序序列的第一个结点 preorder[0] 为根节点，我们在中序序列中找到根节点的位置 i，可以将中序序列划分为左子树 inorder[:i] 和右子树 inorder[i + 1:]。
     * 通过左右子树的区间，可以计算出左、右子树节点的个数，假设为 m、n。然后在前序节点中，从根节点往后的 m 个节点为左子树，再往后的 n 个节点为右子树。递归求解即可。
     *
     * 前序遍历：先遍历根节点，再遍历左子树，最后遍历右子树；
     * 中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树。
     */
    class Solution {
        // 用hashmap存储中序节点的的位置
        private Map<Integer, Integer> indexes = new HashMap<>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            // 将中序节点的位置存进去
            for (int i = 0; i < inorder.length; i++) {
                indexes.put(inorder[i], i);
            }
            return dfs(preorder, 0, 0, preorder.length -1 );
        }

        /**
         * dfs
         * <img src="https://img-blog.csdnimg.cn/20190301205222160.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bl9mZW5namlhbw==,size_16,color_FFFFFF,t_70"/>
         *
         * @param preorder 前序序列
         * @param pre_root 当前根的索引
         * @param in_left  递归树的左边界，即数组左边界
         * @param in_right 递归树的右边界，即数组右边界
         */
        private TreeNode dfs(int[] preorder,  int pre_root, int in_left, int in_right) {
            if (in_left > in_right) {
                return null;
            }
            // 当前根的值
            int root_val = preorder[pre_root];
            // 中序序列中该根节点的索引
            int root_index = indexes.get(root_val);
            TreeNode root = new TreeNode(root_val);
            // 中序序列 index左边的为左子树，index右边的为右子树
            // 左子树的根的索引为前序中的根节点+1
            // 递归左子树的左边界为原来的中序in_left
            // 递归左子树的右边界为中序中的根节点索引-1
            root.left = dfs(preorder, pre_root + 1, in_left, root_index -1);
            // 右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
            // 递归右子树的左边界为中序中当前根节点+1
            // 递归右子树的右边界为中序中原来右子树的边界
            root.right = dfs(preorder, pre_root + 1 + root_index - in_left, root_index + 1,  in_right);
            return root;
        }
    }
}
